package map;

import java.util.*;

/**
 * 要通过此题的LeetCode解，有一些小坑
 * 输入[0,0,0,0] => 如何去重
 */
public class LruImplemention {
    public static void main(String[] args) throws InterruptedException {
        MyLruCache<String, String> lru = new MyLruCache<>(3);
        lru.put("a", "a");
        lru.put("b", "b");
        lru.put("c", "c");
        lru.put("d", "d");
        System.out.println(lru);
    }

    public static class MyLruCache<K,V > extends  LinkedHashMap<K,V>{

        private int maxCap;

        public MyLruCache(int maxCap) {
            this.maxCap = maxCap;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return this.size() > maxCap;
        }
    }




    /**
     * 跑不过
     */
    class Solution1 {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            if (nums == null || nums.length < 3) {
                return ans;
            }
            Arrays.sort(nums);
            Set<String> set = new HashSet<>();
            int left = 0, right = nums.length - 1;

            while ((right - left) > 1) {
                int mid = left + 1;
                if ((nums[left] + nums[mid] + nums[right]) > 0) {
                    --right;
                } else if ((nums[left] + nums[mid] + nums[right]) == 0) {
                    List<Integer> list = addToListAndCheckIsRepeat(nums[left], nums[mid], nums[right], set);
                    if (list != null) {
                        ans.add(list);
                    }
                    --right;
                } else {
                    for (; mid < right; ++mid) {
                        if ((nums[left] + nums[mid] + nums[right]) == 0) {
                            List<Integer> list = addToListAndCheckIsRepeat(nums[left], nums[mid], nums[right], set);
                            if (list != null) {
                                ans.add(list);
                            }
                            --right;
                        }
                    }
                    ++left;
                }
            }
            return ans;
        }

        private List<Integer> addToListAndCheckIsRepeat(int left, int mid, int right, Set<String> set) {
            String tmp = "" + left + mid + right;
            if (!set.contains(tmp)) {
                List<Integer> list = new ArrayList<>();
                list.add(left);
                list.add(mid);
                list.add(right);
                set.add(tmp);
                return list;
            } else {
                set.add(tmp);
                return null;
            }
        }
    }

    /**
     * 用数组来作为map，不能存负数，跑不过
     */
    class Solution2 {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            Arrays.sort(nums);
            int[] map = new int[nums[nums.length - 1] + 1];
            Set<String> set = new HashSet<>();
            Arrays.fill(map, 0);
            for (int num : nums) {
                ++map[num];
            }
            for (int i = 0; i < nums.length; ++i) {
                if (i != 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int target = 0 - nums[i];
                --map[nums[i]];
                List<List<Integer>> tmpAns = twoSun(nums, map, target, i, nums.length - 1);
                if (tmpAns.size() == 0) {
                    ++map[nums[i]];
                } else {
                    for (int j = 0; j < tmpAns.size(); ++j) {
                        int num1 = tmpAns.get(j).get(0);
                        int num2 = tmpAns.get(j).get(1);
                        String str = "" + nums[i] + num1 + num2;
                        if (!set.contains(str)) {
                            List<Integer> list = new ArrayList<>();
                            list.add(nums[i]);
                            list.add(num1);
                            list.add(num2);
                            ans.add(list);
                            set.add(str);
                        } else {
                            set.add(str);
                        }
                    }
                }
            }
            return ans;
        }

        private List<List<Integer>> twoSun(int[] nums, int[] map, int target, int begin, int end) {
            List<List<Integer>> ans = new ArrayList<>();
            for (int i = begin; i <= end; ++i) {
                if (map[target - nums[i]] != 0 && (target - nums[i]) != nums[i]) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(target - nums[i]);
                    ans.add(tmp);
                } else if (map[target - nums[i]] != 0 && (target - nums[i]) == nums[i]) {
                    if (map[target - nums[i]] >= 2) {
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[i]);
                        ans.add(tmp);
                    }
                }
            }
            return ans;
        }
    }

    /**
     * 终于通过了，用set去重
     */
    class Solution3 {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            if (nums == null || nums.length < 3) {
                return ans;
            }
            Arrays.sort(nums);
            Set<String> set = new HashSet<>();
            int left = 0;
            while (left < nums.length - 2) {
                if (nums[left] > 0) {
                    ++left;
                    continue;
                }
                if (left > 0 && (nums[left] == nums[left - 1])) {
                    ++left;
                    continue;
                }
                int mid = left + 1, right = nums.length - 1;
                while (right - left >= 2 && mid < right) {
                    //当mid = left + 1时，如果三数之和加起来大于0，只能移动right指针，
                    if ((nums[left] + nums[mid] + nums[right]) > 0) {
                        --right;
                    } else if ((nums[left] + nums[mid] + nums[right]) == 0) {
                        List<Integer> list = addToListAndCheckIsRepeat(nums[left], nums[mid], nums[right], set);
                        if (list != null) {
                            ans.add(list);
                        }
                        ++mid;
                        --right;
                    } else {
                        //三数之和小于0则不断移动mid指针,直至三数之和不小于0
                        while (mid < right && (nums[left] + nums[mid] + nums[right]) < 0) {
                            if ((nums[left] + nums[mid] + nums[right]) == 0) {
                                List<Integer> list = addToListAndCheckIsRepeat(nums[left], nums[mid], nums[right], set);
                                if (list != null) {
                                    ans.add(list);
                                }
                                --right;
                                ++mid;
                            } else {
                                ++mid;
                            }
                        }
                    }
                }
                ++left;
            }
            return ans;
        }

        private List<Integer> addToListAndCheckIsRepeat(int left, int mid, int right, Set<String> set) {
            String tmp = "" + left + mid + right;
            if (!set.contains(tmp)) {
                List<Integer> list = new ArrayList<>();
                list.add(left);
                list.add(mid);
                list.add(right);
                set.add(tmp);
                return list;
            } else {
                set.add(tmp);
                return null;
            }
        }
    }

    /**
     * 不用set去重
     */
    static class Solution4 {
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> ans = new ArrayList<>();
            if (nums == null || nums.length < 3) {
                return ans;
            }
            Arrays.sort(nums);
            int left = 0;
            while (left < nums.length - 2) {
                if (nums[left] > 0) {
                    ++left;
                    continue;
                }
                //去重
                if (left > 0 && (nums[left] == nums[left - 1])) {
                    ++left;
                    continue;
                }
                int mid = left + 1, right = nums.length - 1;
                while (right - left >= 2 && mid < right) {
                    //当mid = left + 1时，如果三数之和加起来大于0，只能移动right指针，
                    //但是后面的步骤也可以这样吗
                    if ((nums[left] + nums[mid] + nums[right]) > 0) {
                        --right;
                    } else if ((nums[left] + nums[mid] + nums[right]) == 0) {
                        List<Integer> list = addToList(nums[left], nums[mid], nums[right]);
                        ans.add(list);
                        ++mid;
                        --right;
                    } else {
                        //三数之和小于0
                        while (mid < right && (nums[left] + nums[mid] + nums[right]) < 0) {
                            if ((nums[left] + nums[mid] + nums[right]) == 0) {
                                List<Integer> list = addToList(nums[left], nums[mid], nums[right]);
                                ans.add(list);
                                --right;
                                ++mid;
                            } else {
                                ++mid;
                            }
                        }
                    }

                    while (right - left >= 2 && (right <= nums.length - 2 && nums[right] == nums[right + 1])) {
                        --right;
                    }
                    while (mid < right && nums[mid] == nums[mid - 1]) {
                        ++mid;
                    }
                }
                ++left;
            }
            return ans;
        }

        private List<Integer> addToList(int left, int mid, int right) {
            List<Integer> list = new ArrayList<>();
            list.add(left);
            list.add(mid);
            list.add(right);
            return list;
        }
    }

    /**
     * 执行用时20ms
     */
    class Solution5 {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            for (int i = 0; i < nums.length - 2; i++) {
                int left = i + 1, right = nums.length - 1;
                int fixed = nums[i];
                if (fixed > 0) {
                    break;
                }
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                while (left < right) {
                    int sum = fixed + nums[left] + nums[right];
                    if (sum > 0) {
                        right--;
                        //  while(left<right&&nums[right]==nums[right+1])right--;
                    } else if (sum < 0) {
                        left++;
                        // while(left<right&&nums[left]==nums[left-1])left++;
                    } else {
                        // res.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                        List<Integer> t = new ArrayList<>();
                        t.add(fixed);
                        t.add(nums[left]);
                        t.add(nums[right]);
                        res.add(t);
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        left++;
                        right--;
                    }
                }

            }
            return res;
        }
    }


}
